package com.bootcamp.s2_0922.ds.Exercise._0926_Ex;

/**
 * @program: myClassCode
 * @description: list exercise
 * @author: Keyu Li
 * @create: 2021-09-26 20:00
 **/

public class Ex1_List {
    public static void main(String[] args) {
        MyNode<Integer> root1 = new MyNode<>(1,
                new MyNode(3,
                        new MyNode(5,
                                new MyNode(7, null))));
        MyNode<Integer> root2 = new MyNode<>(2,
                new MyNode(4,
                        new MyNode(8,
                                new MyNode(9, null))));
        System.out.println(root1);
        System.out.println(root2);
        MyNode root3 = merge(root1, root2);
        System.out.println(root3);
    }

    private static MyNode merge(MyNode<Integer> root1, MyNode<Integer> root2) {
        // 判断是否存在空链表
        if (root1 == null) return root2;
        if (root2 == null) return root1;
        // 确定根节点
        int com = root1.value.compareTo(root2.value);
        MyNode returnNode;
        MyNode curr;
        if (com < 0) {
            returnNode = root1;
            root1 = root1.next;
        } else {
            returnNode = root2;
            root2 = root2.next;
        }
        curr = returnNode;
        // 遍历两个单独的链表
        while (root1 != null && root2 != null) {
            com = root1.value.compareTo(root2.value);
            if (com < 0) {
                curr.next = root1;
                root1 = root1.next;
            } else {
                curr.next = root2;
                root2 = root2.next;
            }
            curr = curr.next;
        }
        if (root1 == null)
            curr.next = root2;
        if (root2 == null)
            curr.next = root1;
        return returnNode;
    }
}

class MyNode<T extends Comparable<T>> {
    T value;
    MyNode next;

    public MyNode(T value, MyNode next) {
        this.value = value;
        this.next = next;
    }

    @Override
    public String toString() {
        final StringBuffer sb = new StringBuffer("MyNode{");
        sb.append("value=").append(value);
        sb.append(", next=").append(next);
        sb.append('}');
        return sb.toString();
    }
}
